package leetbook.sort_search;

import java.util.ArrayList;
import java.util.List;

/**
 * 维护有序结构，二分查找
 */

public class Solution315 {

    public static void main(String[] args) {

        int[] nums = {-1,-1};
        List<Integer> integers = new Solution315().countSmaller(nums);
        System.out.println(integers);
    }


    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>(n);
        for (int i = n-1; i >= 0; i--) {
            res.add(0,binarySearch(list,nums[i]));
            binaryInsert(list,nums[i]);
        }
        return res;
    }

    /**
     * 在list中插入num，保证list有序
     * 二分查找插入
     * @param list
     * @param num
     */
    public void binaryInsert(ArrayList<Integer> list, int num){
        int low = 0, high = list.size()-1, mid = 0;
        while (low<=high){
            mid = (low+high)>>1;
            int midNum = list.get(mid);
            if(midNum>num){
                high = mid - 1;
            }else if(midNum<num){
                low = mid + 1;
            }else {
                list.add(mid,num);
                return;
            }
        }
        //list里没有num时
        list.add(low,num);
    }

    /**
     * 返回list中比num小的个数
     * 找第一个大于num的数字下标即可
     * @param list
     * @param num
     * @return
     */
    public int binarySearch(List<Integer> list, int num){
        int low = 0, high = list.size()-1, mid = 0;
        while (low<=high){
            mid = (low+high)>>1;
            int midNum = list.get(mid);
            if(midNum>=num){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        return low;
    }
}
